#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        int i1 = -1, i2 = -1;
        int k;
        double ans;
        k = (n1 + n2) / 2;
        if ((n1 + n2) % 2 == 0) k--;
        while (k)
        {
            int t = k / 2;
            if (k == 1)t = 1;
            if (i2 + t >= n2 || (i1 + t < n1 && nums1[i1 + t] <= nums2[i2 + t]))
            {
                i1 += t;
                k -= t;
                continue;
            }
            i2 += t;
            k -= t;
        }
        i1++;
        i2++;
        if (i1 == n1)ans = nums2[i2++];
        else if (i2 == n2)ans = nums1[i1++];
        else ans = nums1[i1] < nums2[i2] ? nums1[i1++] : nums2[i2++];
        if ((n1 + n2) % 2)return ans;
        if (i1 == n1)ans += nums2[i2++];
        else if (i2 == n2)ans += nums1[i1++];
        else ans += nums1[i1] < nums2[i2] ? nums1[i1] : nums2[i2];
        return ans / 2;
    }
};

int main()
{
    int a[] = { 1,2 };
    int b[] = { 3,4 };
    vector<int> aa(a, a + 2);
    vector<int> bb(b, b + 2);
    string ss;
    Solution s;
    cout << s.findMedianSortedArrays(aa, bb) << endl;
}